import random

class RandomizedCollection(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dict = {}
        self.list = []

    def insert(self, val):
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        i = len(self.list)
        self.list.append(val)
        if val not in self.dict:
            self.dict.update({val:[]})
            self.dict[val].append(i)
            return True
        else:
            self.dict[val].append(i)
            return False

    def remove(self, val):
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.dict:
            slots = self.dict[val]
            i = slots.pop()
            if len(slots)==0:
                del self.dict[val]
            if i!=len(self.list)-1:
                toMove = self.list[-1]
                self.list[i] = toMove
                self.dict[toMove].remove(len(self.list)-1)
                self.dict[toMove].append(i)
            self.list.pop()
            return True
        else:
            return False

    def getRandom(self):
        """
        Get a random element from the collection.
        :rtype: int
        """
        i = int(random.random()*len(self.list))
        return self.list[i]

# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()